public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    public int numDistinct(String s, String t) {
        /**
         * 不同的子序列
         * 解法：
         *  典型的动归解决子序列问题，但是存在大量搜索*/
        // 初始化
        int n = s.length(), m = t.length();
        int[][] memo = new int[n][m];
        // 执行逻辑
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // -1 表示没有计算过
                memo[i][j] = -1;
            }
        }
        // 返回值
        return dfs(n - 1, m - 1, s.toCharArray(), t.toCharArray(), memo);
    }

    private int dfs(int i, int j, char[] s, char[] t, int[][] memo) {
        /**
         * 动规解决重复子问题*/
        if (i < j) {
            return 0;
        }
        if (j < 0) {
            return 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int res = dfs(i - 1, j, s, t, memo);
        if (s[i] == t[j]) {
            res += dfs(i - 1, j - 1, s, t, memo);
        }
        return memo[i][j] = res;
    }
}
